package org.movee.jalgo.sort;

/**
 * 希尔排序
 *
 * @author 54740559@qq.com
 * @version 1.0
 *
 */
public class ShellSort {

    public static int[] sort(int[] arr) {

        int len = arr.length;
        int h = 1;
        // 计算初始步长
        while (h < len / 3) {
            h = 3 * h + 1;
        }

        while (h >= 1) {

            // 对h个子数组进行排序
            for (int i = h; i < len; i++) {
                // 从位置i的前一位开始比较
                int curr = arr[i];
                // j是curr应该插入的位置
                int j = i;
                // 注意结束条件是j>=h
                for (; j >=h && curr < arr[j - h]; j = j - h) {
                    arr[j] = arr[j - h];
                }
                arr[j] = curr;
            }

            // 减少步长，直到等于1
            h = h / 3;

        }

        return arr;
    }

}
